package com.zx._12_算法.排序;

import com.zx._12_算法.Arrs.IAS;

/**
 * @version v1.0
 * @Project: knowledge
 * @Title: Sort3
 * @Description: No.3 插入排序
 *         插入排序的思想和我们打扑克摸牌的时候一样，从牌堆里一张一张摸起来的牌都是乱序的，
 *         我们会把摸起来的牌插入到左手中合适的位置，让左手中的牌时刻保持一个有序的状态。
 *         那如果我们不是从牌堆里摸牌，而是左手里面初始化就是一堆乱牌呢？
 *         一样的道理，我们把牌往手的右边挪一挪，把手的左边空出一点位置来，然后在乱牌中抽一张出来，插入到左边，再抽一张出来，插入到左边，
 *         再抽一张，插入到左边，每次插入都插入到左边合适的位置，时刻保持左边的牌是有序的，直到右边的牌抽完，则排序完毕。
 *         时间复杂度：O(n^2)
 * @author: zhangxue
 * @date: 2019年7月7日下午9:27:41
 * @company: 未知之地
 * @Copyright: Copyright (c) 2019
 */
public class Sort3_插入排序 implements IAS {

    @Override
    public void sort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            // 默认插入的位置
            int j = i - 1;
            // 需要插入的数据
            int num = nums[i];

            for (; j >= 0; j--) {
                if (num >= nums[j]) {
                    break;
                } else {
                    nums[j + 1] = nums[j];
                }
            }
            // for最后一次--后，跳出循环，需要 + 1
            nums[j + 1] = num;
        }
    }
}
